from typing import List


class Solution:
    """找O的时候越界返回
        如果没越界表示被包围了
    """

    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        if not board:
            return []
        m = len(board)
        n = len(board[0])
        visited = [([False] * n) for i in range(m)]

        d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        sign = False

        def valid_area(x: int, y: int):
            # 是否是合法的坐标
            return x >= 0 and y >= 0 and x < m and y < n

        def backtrack(x: int, y: int, region: List[int]):
            nonlocal sign

            visited[x][y] = True
            region += [(x, y)]
            for i in d:
                new_x = x + i[0]
                new_y = y + i[1]
                if not valid_area(new_x, new_y):
                    sign = True
                    # print("sign0", sign)
                else:
                    if board[new_x][new_y] == "O" and not visited[new_x][new_y]:
                        backtrack(new_x, new_y, region)

        for i in range(m):
            for j in range(n):
                if board[i][j] == "O" and not visited[i][j]:
                    region = []
                    sign = False
                    backtrack(i, j, region)
                    if not sign:
                        for x, y in region:
                            board[x][y] = "X"


if __name__ == "__main__":
    regions = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
    # regions = [["X","O","X"],["X","O","X"],["X","O","X"]]
    Solution().solve(regions)
    print(regions)
